Intra mode prediction is used for both intra and inter frames. In intra frames, all macroblocks are coded in intra modes. For inter frames (P and B frames) both inter and intra prediction are used in the H.264 Standard (also known as JVT and MPEG-4 AVC). Each individual macroblock is either coded as intra, i.e. using only spatial correlation, or coded as inter, i.e. using temporal correlation from previously coded frames. In general, an encoder may make an inter/intra coding decision for each macroblock based on coding efficiency and subjective quality considerations. Inter coding is typically used for macroblocks that are well predicted from previous pictures, and intra coding is typically used for macroblocks that are not well predicted from previous pictures, and/or for macroblocks with low spatial activity.
In the H.264 standard, inter coding allows various block partitions (e.g., 16×16, 16×8, 8×16, and 8×8 for a macroblock, and 8×8, 8×4, 4×8, 4×4 for an 8×8 sub-macroblock partition) and multiple reference pictures to be used for predicting a 16×16 macroblock. Furthermore, JVT also supports SKIP and DIRECT modes.
For intra prediction, the following two block types are supported: INTRA 4×4; and INTRA 16×16.
Turning to FIG. 1A, INTRA 4×4 prediction modes are indicated generally by the reference numeral 100. The INTRA 4×4 prediction modes 100 include a vertical mode 0, a horizontal mode 1, a DC mode 2, a diagonal-down/left mode 3, a diagonal down/right mode 4, a vertical-right mode 5, a horizontal-down mode 6, a vertical-left mode 7, and a horizontal-up mode 8.
Turning to FIG. 1B, INTRA 16×16 prediction modes are indicated generally by the reference numeral 150. The INTRA 16×16 prediction modes 150 include a vertical mode 0, a horizontal mode 1, a DC mode 2, and a PLANE mode 3.
In the prior art, a rate distortion optimization (RDO) framework is used for mode decisions. For inter modes, motion estimation is separately considered from mode decision. Motion estimation is first performed for all block types of inter modes, then the mode decision is made by comparing the cost of each inter mode and intra mode. The mode with the minimal cost is selected as the best mode.
A conventional procedure to encode one macroblock s in an intra coded (I) picture is summarized as follows. This procedure is hereinafter referred to as the “conventional macroblock encoding procedure”.
In a first step of the conventional macroblock encoding procedure, the following are provided: the last decoded pictures, the Lagrangian multiplier λMODE, λMOTION, and the macroblock quantizer QP.
In a second step of the conventional macroblock encoding procedure, the macroblock intra prediction mode is chosen by minimizing J(s, c, MODE|QP,λMODE)=SSD(s, c, MODE|QP)+λMODE·R(s, c, MODE|QP), given QP and λMODE when varying MODE. Symbol c represents the reconstructed macroblock. Symbol SSD represents the Sum of Square Differences between the original signal and the reconstructed signal. Symbol R(s, c, MODE) represents the number of bits associated with choosing MODE, including the bits for the macroblock header and all DCT coefficients. Symbol MODE represents a mode out of the set of potential macroblock modes:MODEε55 INTRA4×4,INTRA16×16}                The INTRA 4×4 modes include:        
  MODE  ∈      {                                        vertical            ,                                                  ⁢            horizontal            ,                                                            DC            ,                                                  ⁢                          diagonal              -                              down                /                left                                      ,                                                                          diagonal              -                              down                /                right                                      ,                                                                          vertical              -              left                        ,                                                                          horizontal              -              down                        ,                                                                          vertical              -              right                        ,                                                            horizontal            -            up                                }                  The INTRA 16×16 modes include:MODEε{vertical,horizontal,DC,plane}        
To encode one macroblock s in an inter-coded (P or B) picture, the following two additional steps are employed.
The first additional step involves performing motion estimation and reference picture selection by minimizingJ(REF,m(REF)|λMOTION)=SAD(s,c(REF,m(REF)))+λMOTION·(R(m(REF)−p(REF))+R(REF))for each reference picture and motion vector of a possible macroblock mode. In the equation, m represents the current motion vector being considered, REF represents the reference picture, p represents the motion vector used for the prediction during motion vector coding, R(m−p) represents the bits used for coding the motion vector, and R(REF) represents the bits for coding the reference picture. SAD represents the Sum of Absolute Differences between the original signal and the reference signal predicted by the motion vector.
The second additional step involves choosing the macroblock prediction mode by minimizingJ(s,c,MODE|QP,λMODE)=SSD(s,c,MODE|QP)+λMODE·R(s,c,MODE|QP),given QP and λMODE when varying MODE. R(s, c, MODE) includes the bits for the macroblock header, the motion and all DCT coefficients. MODE represents a mode out of the set of potential macroblock modes:
            P      ⁢              -            ⁢      frame      ⁢              :            ⁢                          ⁢      MODE        ∈          {                                                                                                                                                                                                            INTRA                            ⁢                                                                                                                  ⁢                            4                            ×                            4                                                    ,                                                      INTRA                            ⁢                                                                                                                  ⁢                            16                            ×                            16                                                    ,                                                                                                                                                              SKIP                          ,                                                                                                                                                                                                            16                      ×                      16                                        ,                                          16                      ×                      8                                        ,                                                                                                                                          8                ×                16                            ,                              8                ×                8                            ,                                                                                          8                ×                4                            ,                              4                ×                8                            ,                                                                          4              ×              4                                          }        ,          ⁢            B      ⁢              -            ⁢      frame      ⁢              :            ⁢                          ⁢      MODE        ∈                  {                                                                              INTRA                  ⁢                                                                          ⁢                  4                  ×                  4                                ,                                  INTRA                  ⁢                                                                          ⁢                  16                  ×                  16                                ,                                                                                        BIDIRECT                ,                DIRECT                ,                                                                                                          FWD                  ⁢                                                                          ⁢                  16                  ×                  16                                ,                                  FWD                  ⁢                                                                          ⁢                  16                  ×                  8                                ,                                                                                                          FWD                  ⁢                                                                          ⁢                  8                  ⁢                                                                          ×                  16                                ,                                  FWD                  ⁢                                                                          ⁢                  8                  ×                  8                                ,                                                                                                          FWD                  ⁢                                                                          ⁢                  8                  ×                  4                                ,                                  FWD                  ⁢                                                                          ⁢                  4                  ×                  8                                ,                                                                                                          FWD                  ⁢                                                                          ⁢                  4                  ×                  4                                ,                                  BAK                  ⁢                                                                          ⁢                  16                  ×                  16                                ,                                                                                                          BAK                  ⁢                                                                          ⁢                  16                  ×                  8                                ,                                                                  ⁢                                  BAK                  ⁢                                                                          ⁢                  8                  ×                  16                                ,                                                                                                          BAK                  ⁢                                                                          ⁢                  8                  ×                  8                                ,                                  BAK                  ⁢                                                                          ⁢                  8                  ×                  4                                ,                                                                                                          BAK                  ⁢                                                                          ⁢                  4                  ×                  8                                ,                                  BAK                  ⁢                                                                          ⁢                  4                  ×                  4                                                                    }            .      
It is to be appreciated that, for an I picture, the second step of the conventional macroblock encoding procedure is employed in place of the preceding second additional step.
In the prior art, in particular, in relation to the conventional macroblock encoding procedure described above, a picture is first analyzed using edge detection as in FIGS. 2A and 2B. Only modes with orientations closer to the dominant edge direction are examined.
Turning to FIG. 2A, a method for performing mode decision for an INTRA 16×16 luma sample using edge information is indicated generally by the reference numeral 200. The method 200 includes a start block 202 that passes control to a function block 205. The function block 205 obtains an edge direction histogram, and passes control to a function block 210. The function block 210 checks the mode with the maximum amplitude in the edge direction histogram and two adjacent modes, and passes control to a decision block 215. The decision block 215 determines whether or not all of the amplitudes (of the mode with the maximum amplitude and the two adjacent modes) are similar. If all of the amplitudes are not similar, then control is passes to a function block 220. Otherwise, if all of the amplitudes are similar, then control is passes to a function block 230.
The function block 220 chooses the best INTRA 16×16 (luma) prediction mode of the tested modes, and passes control to an end block 225.
The decision block 230 checks the DC mode, and passes control to function block 220.
Turning to FIG. 2B, a method for performing mode decision for an INTRA 4×4 sample using edge information is indicated generally by the reference numeral 250.
The method 250 includes a start block 252 that passes control to a function block 255. The function block 255 obtains an edge direction histogram, and passes control to a function block 260. The function block 260 checks the mode with the maximum amplitude in the edge direction histogram, and passes control to a decision block 265. That is, the function block 260 checks the maximum amplitude in one direction and then checks the amplitudes in the other directions to determine, in conjunction with decision block 265, whether we want to check DC modes. The decision block 265 determines whether or not all of the amplitudes are similar. If all of the amplitudes are not similar, then control is passes to a function block 270. Otherwise, if all of the amplitudes are similar, then control is passes to a function block 280.
The function block 270 chooses the best INTRA 4×4 prediction mode of the tested modes, and passes control to an end block 275.
The decision block 280 checks the DC mode, and passes control to function block 270.
With respect to another prior art approach, for inter frames, SKIP mode and 16×16 mode are examined first. If the distortion is small enough (either SKIP mode or 16×16 mode is already a good mode for this macroblock), then not all sub-modes for INTRA 4×4 need to be tested. Accordingly, the search may be terminated faster without much impact in quality. Thus, this approach reduces the complexity of intra mode decision by using information from inter coding. This approach is shown and described with respect to FIG. 3.
Turning to FIG. 3, a method for mixed inter-intra mode decision is indicated generally by the reference numeral 300. The method 300 includes a start block 302 that passes control to a function block 304. The function block 304 checks SKIP mode and 16×16 mode, and passes control to a decision block 306. The decision block 306 determines whether or not MC2>T1, where MC2=min(J(SKIP), J(16×16)), the minimum distortion between SKIP mode and 16×16 mode, and T1 is the first threshold. If MC2<=T1, then control is passed to a decision block 308. Otherwise, if MC2=min(J(SKIP), J(16×16))>T1, then control is passed to a function block 310 and a function block 312.
The decision block 308 determines whether or not MC2 is greater than T2 (a second threshold). If MC2 is not greater than T2, then control is passed to function block 310 and function block 312. Otherwise, if MC2 is greater than T2, then control is passed to a function block 318.
The function block 310 checks other inter modes, and passes control to a function block 312. The function block 312 checks other non-tested intra modes, and passes control to a function block 314. The function block 314 selects the best mode from among the evaluated modes, and passes control to an end block 316. The end block 316 ends the macroblock encoding.
The function block 318 checks the INTRA 4×4 DC, and passes control to a decision block 320. The decision block 320 determines whether or not J(INTRA 4×4 DC) is less than a*MC2+b, where a and b are constants. If J(INTRA 4×4 DC) is not less than a*MC2+b, then control is passed to function block 310 and function block 312. Otherwise, if J(INTRA 4×4 DC) is less than a*MC2+b, then control is passed to the function block 312.
Accordingly, it would be desirable and highly advantageous to have a method and apparatus for fast intra mode prediction for a video encoder that overcomes the above-described problems of the prior art.